
/**
 * 
 * MVP争夺战
 * 
 * 题目描述

在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到 MVP，MVP 的条件是单场最高分得分获得者。

可以并列所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，然而比赛过程中的每一分钟的得分都只能由某一个人包揽。

输入描述
输入第一行为一个数字 t ，表示为有得分的分钟数

1 ≤ t ≤ 50
第二行为 t 个数字，代表每一分钟的得分 p

1 ≤ p ≤ 50
输出描述
输出有得分的队员都是 MVP 时，最少得 MVP 得分。

用例
输入	9
5 2 1 5 2 1 5 2 1
输出	6
说明	样例解释 一共 4 人得分，分别都是 6 分
5 + 1 ， 5 + 1 ， 5 + 1 ， 2 + 2 + 2

 */

import java.util.LinkedList;
import java.util.Scanner;

/**
  * 
  题目解析
本题和

LeetCode - 698 划分为k个相等的子集_伏城之外的博客-CSDN博客

属于同一类问题，解法相同，题解请看上面博客：划分k个相等的子集

题目解析
本题其实是一道子集问题，可以利用回溯法求解。

首先，我们可以求出nums数组的所有元素之和sum，如果sum % k 不为0的话，说明每一份子集的和不是整数，但是题目说了nums数组中的元素都是整数，因此每一个子集的和也应该是整数，因此如果sum % k 不为0的话，则返回false。

如果sum % k 为0，则我们假设subSum = sum / k，即每一个子集的和为subSum，那么subSum应该大于等于nums数组的最大值，因为nums数组的每一个子集至少有一个元素组成，因此subSum应该大于或等于每一个nums元素，即至少不小于nums数组的最大值。

当面两个条件都符合后，还不能说明nums可以被分为k个和相等的子集，比如nums=[2,2,2,2,3,4,5] ，且k=4。

nums数组的和sum = 20，k=4，因此subSum = 5,而subSum >= max(nums[i]) = 5，因此符合上面两个条件，但是nums数组却无法分为4个等和子集。

因此，我们需要一种算法来判断一个数组是否可以划分k个和相等的子集，此时我们就需要借助回溯算法。

我们可以想象划分子集问题，可以看成向k个桶中放球，每个桶的承重为subSum，而现在nums中存放着重量不一的多个球，如果nums中的球都能放到k个桶中，则可以划分子集成功。

比如nums = [4, 3, 2, 3, 5, 2, 1], k = 4，对应的subSum=5



首先，nums的重量5的球可以独占一个桶，我们可以减少考虑一个桶的处理



 接下来，我们需要将球按照降序排序，然后依次放入桶中



 



由于 4 + 3 > 5，因此球3需要放到下一个桶中



同理处理下面的球








  */
public class MVP争夺战 {
    
    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
 
        int m = sc.nextInt();
 
        LinkedList<Integer> link = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            link.add(sc.nextInt());
        }
 
        System.out.println(solution(link, m));
    }
 
    public static int solution(LinkedList<Integer> link, int m) {
        link.sort((a, b) -> b - a);
 
        int sum = 0;
        for (Integer ele : link) {
            sum += ele;
        }
 
        while (m >= 1) {
            // 由于canPartition方法中会删除link元素，因此我们不能直接传递link过去，需要传递link备份，否则会影响下一次count判断
            LinkedList<Integer> link_cp = new LinkedList<>(link);
            if (canPartitionMSubsets(link_cp, sum, m)) return sum / m;
            m--;
        }
 
        return sum;
    }
 
    public static boolean canPartitionMSubsets(LinkedList<Integer> link, int sum, int m) {
        if (sum % m != 0) return false;
 
        int subSum = sum / m;
 
        if (subSum < link.get(0)) return false;
 
        //    while (link.get(0) == subSum) { // 此段代码可能会出现越界
        while (!link.isEmpty() && link.get(0) == subSum) {
            link.removeFirst();
            m--;
        }
 
        int[] buckets = new int[m];
        return partition(link, 0, buckets, subSum);
    }
 
    public static boolean partition(LinkedList<Integer> link, int index, int[] buckets, int subSum) {
        if (index == link.size()) return true;
 
        int select = link.get(index);
 
        for (int i = 0; i < buckets.length; i++) {
            if (i > 0 && buckets[i] == buckets[i - 1]) continue;
            if (select + buckets[i] <= subSum) {
                buckets[i] += select;
                if (partition(link, index + 1, buckets, subSum)) return true;
                buckets[i] -= select;
            }
        }
 
        return false;
    }
}
